import java.util.List;


public class MySingleList {

    static class ListNode {
        public int val;//存储的数据
        public ListNode next;//存储下一个节点的地址
        public ListNode() {

        }
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;// 代表当前链表的头节点的引用


    public void createLink() {
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(45);
        ListNode listNode3 = new ListNode(23);
        ListNode listNode4 = new ListNode(90);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4; /* */
        head = listNode1;
    }


    /**
     * 遍历链表
     */
    public void display() {
        //如果说 把整个链表 遍历完成 那么 就需要 head == null
        // 如果说 你遍历到链表的尾巴  head.next == null
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 从指定位置开始打印链表
     * @param newHead
     */
    public void display(ListNode newHead) {
        //如果说 把整个链表 遍历完成 那么 就需要 head == null
        // 如果说 你遍历到链表的尾巴  head.next == null
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度 O(N)
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法 O(1)
    public void addFirst(int data){
        ListNode listNode = new ListNode(data);
        listNode.next = head;
        head = listNode;
    }
    //尾插法 O(N)    找尾巴的过程
    public void addLast(int data){
        ListNode listNode = new ListNode(data);
        if(head == null) {
            head = listNode;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = listNode;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data)
            throws ListIndexOutOfException{
        checkIndex(index);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndexSubOne(index);
        ListNode listNode = new ListNode(data);
        listNode.next = cur.next;
        cur.next = listNode;
    }

    /**
     * 找到 index-1位置的节点的地址
     * @param index
     * @return
     */
    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        int count = 0;
        while (count != index-1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }
    private void checkIndex(int index) throws ListIndexOutOfException{
        if(index < 0 || index > size()) {
            throw new ListIndexOutOfException("index位置不合法");
        }
    }

    //删除第一次出现关键字为key的节点 O(N)
    public void remove(int key){
        if(head == null) {
            return ;//一个节点都没有
        }
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if(cur == null) {
            return;
        }
        ListNode del = cur.next;//要删除的节点
        cur.next = del.next;
    }

    /**
     * 找到关键字key的前一个节点
     * @param key
     * @return
     */
    private ListNode searchPrev(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;//没有你要删除的节点
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head == null) {
            return;
        }
        /*while(head.val == key) {
            head = head.next;
        }*/
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key) {
            head = head.next;
        }
    }

    /**
     * 保证链表当中 所有的节点 都可以被回收
     */
    public void clear() {
        head = null;
    }

    public ListNode reverseList() {
        if(head == null) {
            return null;
        }
        //说明 只有一个节点
        if(head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;

        while (cur != null) {
            ListNode curNext = cur.next;
            //头插法 插入cur
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    public ListNode middleNode() {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode findKthToTail(int k) {
        if(k <= 0 || head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        //1. fast走k-1步
        while (k-1 != 0) {
            fast = fast.next;
            if(fast == null) {
                return null;
            }
            k--;
        }
        //2、3、
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    public boolean chkPalindrome() {
        if(head == null) {
            return false;
        }
        if(head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        //1、找中间节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2、 翻转
        ListNode cur = slow.next;//代表当前需要翻转的节点
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3、一个从头往后  一个从后往前
        while (slow != head) {
            if(head.val != slow.val) {
                return false;
            }
            //偶数的情况
            if(head.next == slow) {
                return true;
            }
            slow = slow.next;
            head = head.next;

        }
        return true;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead;
        ListNode tmp;
        if (list1 ==null){
            return list2;
        }
        if (list2 == null){
            return  list1;
        }
        if (list1.val <= list2.val){
            newHead=list1;
            tmp=list1;
            list1= list1.next;
        }else{
            newHead=list2;
            tmp=list2;
            list2= list2.next;
        }

        while (list1 !=null && list2 !=null){
            if (list1.val <= list2.val){
                tmp.next=list1;
                list1= list1.next;
                tmp=tmp.next;

            }else{
                tmp.next=list2;
                list2= list2.next;
                tmp=tmp.next;
            }
        }
        if (list1 !=null){
            tmp.next=list1;
        }
        if (list2 !=null){
            tmp.next=list2;
        }
        return newHead;

    }
    public ListNode reverseList(ListNode head) {
        //给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
        //解法头插法
        if (head == null){
            return null;
        }
        if (head.next ==null){
            return head;
        }

        ListNode cur=head.next;
        head.next=null;
        while (cur !=null){
            ListNode curNext = cur.next;
            //头插法 插入cur
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;

    }
    public ListNode middleNode(ListNode head) {
        //给定一个头结点为 head 的非空单链表，返回链表的中间结点。
        //如果有两个中间结点，则返回第二个中间结点。
        //解法：快慢指针
        if (head == null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast !=null && fast.next != null){
            fast= fast.next.next;
            slow=slow.next;
        }
        return slow;

    }
    public ListNode FindKthToTail(ListNode head,int k) {
        //输入一个链表，输出该链表中倒数第k个结点。
        //解法：快慢指针
        if ( head == null || k<=0){
            return  null;
        }

        ListNode fast=head;
        ListNode slow=head;
        while (k-1 > 0){
            fast=fast.next;
            if (fast == null){
                return null;
            }
            k--;
        }
        while (fast.next !=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    //根据一个值分割链表，当不改变之前的引用顺序
    public ListNode partition(ListNode head,int val){
        ListNode cur=head;
        ListNode bs=null;//相当于头结点
        ListNode be=null;
        ListNode as=null;//相当于头结点
        ListNode ae=null;

        if (head==null)return null;
        while (cur!=null){
            if (cur.val<val){
                if (bs==null){
                    bs=cur;
                    be=cur;
                }else {
                    be.next=cur;
                    be=be.next;
                }
            }else {
                if (as==null){
                    as=cur;
                    ae=cur;
                }else {
//                    不为空，利用尾插法插入进去
                    ae.next=cur;
                    ae=ae.next;
                }

            }
            cur= cur.next;
        }
        if (bs==null) {
            return as;
        }
//        将链表合并
        be.next=as;
        //防止空指针异常
        if (as!=null){
            ae.next=null;
        }
        return bs;
    }
//    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode curA=headA;
        ListNode curB=headB;
        //循环结束条件，要么找到相等节点，要么俩个都为空也算相等
        while (curA != curB){
            if (curA==null){
                curA=headB;
            }else {
                curA=curA.next;
            }
            if (curB==null){
                curB=headA;
            }else {
                curB=curB.next;
            }
        }
        return curA;
    }
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            if (fast==slow){
                return true;
            }
            fast=fast.next.next;
            slow=slow.next;
        }
        return false;
    }
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //if不能写在首行，因为都等于head
            if (fast == slow) {
                break;
            }
        }
        if (fast==null||fast.next==null){
            return null;
        }
        fast=head;
        while (fast != slow) {
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }



}